<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en-us" lang="en-us">
<head>
  <link href="//gmpg.org/xfn/11" rel="profile">
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <meta name="generator" content="Hugo 0.68.3" />

  
  <meta name="viewport" content="width=device-width, initial-scale=1.0">

  <title>Python数据结构----链表 &middot; 我的博客</title>

  
  <link type="text/css" rel="stylesheet" href="/my_technology_blog/css/print.css" media="print">
  <link type="text/css" rel="stylesheet" href="/my_technology_blog/css/poole.css">
  <link type="text/css" rel="stylesheet" href="/my_technology_blog/css/syntax.css">
  <link type="text/css" rel="stylesheet" href="/my_technology_blog/css/hyde.css">
    <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Abril+Fatface|PT+Sans:400,400i,700">


  
  <link rel="apple-touch-icon-precomposed" sizes="144x144" href="/apple-touch-icon-144-precomposed.png">
  <link rel="shortcut icon" href="/favicon.png">

  
  
</head>

  <body class="theme-base-0b ">
  <aside class="sidebar">
  <div class="container sidebar-sticky">
    <div class="sidebar-about">
      <a href="/my_technology_blog/"><h1>我的博客</h1></a>
      <p class="lead">
       杨博的博客 
      </p>
    </div>

    <nav>
      <ul class="sidebar-nav">
        <li><a href="/my_technology_blog/">Home</a> </li>
        
      </ul>
    </nav>

    <p>&copy; 2021. All rights reserved. </p>
  </div>
</aside>

    <main class="content container">
    <div class="post">
  <h1>Python数据结构----链表</h1>
  <time datetime=2020-06-09T17:00:26&#43;0800 class="post-date">Tue, Jun 9, 2020</time>
  <h2 id="一链表简介">一、链表简介</h2>
<p>链表是一种在存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现。链表是由一系列的结点组成，结点可以在运行时动态生成。每个结点包含两部分：数据域与指针域。数据域存储数据元素，指针域存储下一结点的指针。</p>
<h2 id="二单向链表">二、单向链表</h2>
<p>单向链表也叫单链表，是链表中最简单的形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。</p>
<p><img src="C:%5Cwww%5Chugo_blog%5Cpublic%5Cimg%5Cdanlian.jpg" alt="单向链表数据结构"></p>
<p>head 保存首地址，item 存储数据，next 指向下一结点地址。</p>
<p>链表失去了序列的随机读取优点，同时链表增加了指针域，空间开销也较大，但它对存储空间的使用要相对灵活。</p>
<p>列如：有一堆数据[1,2,3,5,6,7]，要在3和5之间插入4, 如果用数组，需要将5之后的数据都往后退一位，然后再插入4，这样非常麻烦，但是如果用链表，我就直接在3和5之间插入4就行。</p>
<h3 id="1-定义结点">1. 定义结点</h3>
<p>结点的数据结构为数据元素(item)与 指针(next)</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">Node</span>(object):
    <span style="color:#e6db74">&#34;&#34;&#34;单链表的结点&#34;&#34;&#34;</span>

    <span style="color:#66d9ef">def</span> __init__(self, item):
        <span style="color:#75715e"># item存放数据元素</span>
        self<span style="color:#f92672">.</span>item <span style="color:#f92672">=</span> item
        <span style="color:#75715e"># next是下一个节点的标识</span>
        self<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> None
</code></pre></div><h3 id="2-定义链表">2. 定义链表</h3>
<p>链表需要具有首地址指针head。</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">SingleLinkList</span>(object):
    <span style="color:#e6db74">&#34;&#34;&#34;单链表&#34;&#34;&#34;</span>

    <span style="color:#66d9ef">def</span> __init__(self):
        self<span style="color:#f92672">.</span>_head <span style="color:#f92672">=</span> None
</code></pre></div><p>示例：创建链表</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python3" data-lang="python3"><span style="color:#66d9ef">if</span> __name__ <span style="color:#f92672">==</span> <span style="color:#e6db74">&#39;__main__&#39;</span>:
    <span style="color:#75715e"># 创建链表</span>
    link_list <span style="color:#f92672">=</span> SingleLinkList()
    <span style="color:#75715e"># 创建结点</span>
    node1 <span style="color:#f92672">=</span> Node(<span style="color:#ae81ff">1</span>)
    node2 <span style="color:#f92672">=</span> Node(<span style="color:#ae81ff">2</span>)

    <span style="color:#75715e"># 将结点添加到链表</span>
    link_list<span style="color:#f92672">.</span>_head <span style="color:#f92672">=</span> node1
    <span style="color:#75715e"># 将第一个结点的next指针指向下一结点</span>
    node1<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> node2

    <span style="color:#75715e"># 访问链表</span>
    print(link_list<span style="color:#f92672">.</span>_head<span style="color:#f92672">.</span>item)  <span style="color:#75715e"># 访问第一个结点数据</span>
    print(link_list<span style="color:#f92672">.</span>_head<span style="color:#f92672">.</span>next<span style="color:#f92672">.</span>item)  <span style="color:#75715e"># 访问第二个结点数据</span>
</code></pre></div><p>是不是感觉很麻烦，所以我们要在链表中增加操作方法。</p>
<ul>
<li>is_empty() 链表是否为空</li>
<li>length() 链表长度</li>
<li>items() 获取链表数据迭代器</li>
<li>add(item) 链表头部添加元素</li>
<li>append(item) 链表尾部添加元素</li>
<li>insert(pos, item) 指定位置添加元素</li>
<li>remove(item) 删除节点</li>
<li>find(item) 查找节点是否存在</li>
</ul>
<p>代码如下：</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">SingleLinkList</span>(object):
    <span style="color:#e6db74">&#34;&#34;&#34;单链表&#34;&#34;&#34;</span>

    <span style="color:#66d9ef">def</span> __init__(self):
        self<span style="color:#f92672">.</span>_head <span style="color:#f92672">=</span> None

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">is_empty</span>(self):
        <span style="color:#e6db74">&#34;&#34;&#34;判断链表是否为空&#34;&#34;&#34;</span>
        <span style="color:#66d9ef">return</span> self<span style="color:#f92672">.</span>_head <span style="color:#f92672">is</span> None

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">length</span>(self):
        <span style="color:#e6db74">&#34;&#34;&#34;链表长度&#34;&#34;&#34;</span>
        <span style="color:#75715e"># 初始指针指向head</span>
        cur <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
        count <span style="color:#f92672">=</span> <span style="color:#ae81ff">0</span>
        <span style="color:#75715e"># 指针指向None 表示到达尾部</span>
        <span style="color:#66d9ef">while</span> cur <span style="color:#f92672">is</span> <span style="color:#f92672">not</span> None:
            count <span style="color:#f92672">+=</span> <span style="color:#ae81ff">1</span>
            <span style="color:#75715e"># 指针下移</span>
            cur <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next
        <span style="color:#66d9ef">return</span> count

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">items</span>(self):
        <span style="color:#e6db74">&#34;&#34;&#34;遍历链表&#34;&#34;&#34;</span>
        <span style="color:#75715e"># 获取head指针</span>
        cur <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
        <span style="color:#75715e"># 循环遍历</span>
        <span style="color:#66d9ef">while</span> cur <span style="color:#f92672">is</span> <span style="color:#f92672">not</span> None:
            <span style="color:#75715e"># 返回生成器</span>
            <span style="color:#66d9ef">yield</span> cur<span style="color:#f92672">.</span>item
            <span style="color:#75715e"># 指针下移</span>
            cur <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">add</span>(self, item):
        <span style="color:#e6db74">&#34;&#34;&#34;向链表头部添加元素&#34;&#34;&#34;</span>
        node <span style="color:#f92672">=</span> Node(item)
        <span style="color:#75715e"># 新结点指针指向原头部结点</span>
        node<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
        <span style="color:#75715e"># 头部结点指针修改为新结点</span>
        self<span style="color:#f92672">.</span>_head <span style="color:#f92672">=</span> node

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">append</span>(self, item):
        <span style="color:#e6db74">&#34;&#34;&#34;尾部添加元素&#34;&#34;&#34;</span>
        node <span style="color:#f92672">=</span> Node(item)
        <span style="color:#75715e"># 先判断是否为空链表</span>
        <span style="color:#66d9ef">if</span> self<span style="color:#f92672">.</span>is_empty():
            <span style="color:#75715e"># 空链表，_head 指向新结点</span>
            self<span style="color:#f92672">.</span>_head <span style="color:#f92672">=</span> node
        <span style="color:#66d9ef">else</span>:
            <span style="color:#75715e"># 不是空链表，则找到尾部，将尾部next结点指向新结点</span>
            cur <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
            <span style="color:#66d9ef">while</span> cur<span style="color:#f92672">.</span>next <span style="color:#f92672">is</span> <span style="color:#f92672">not</span> None:
                cur <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next
            cur<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> node

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">insert</span>(self, index, item):
        <span style="color:#e6db74">&#34;&#34;&#34;指定位置插入元素&#34;&#34;&#34;</span>
        <span style="color:#75715e"># 指定位置在第一个元素之前，在头部插入</span>
        <span style="color:#66d9ef">if</span> index <span style="color:#f92672">&lt;=</span> <span style="color:#ae81ff">0</span>:
            self<span style="color:#f92672">.</span>add(item)
        <span style="color:#75715e"># 指定位置超过尾部，在尾部插入</span>
        <span style="color:#66d9ef">elif</span> index <span style="color:#f92672">&gt;</span> (self<span style="color:#f92672">.</span>length() <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span>):
            self<span style="color:#f92672">.</span>append(item)
        <span style="color:#66d9ef">else</span>:
            <span style="color:#75715e"># 创建元素结点</span>
            node <span style="color:#f92672">=</span> Node(item)
            cur <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
            <span style="color:#75715e"># 循环到需要插入的位置</span>
            <span style="color:#66d9ef">for</span> i <span style="color:#f92672">in</span> range(index <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span>):
                cur <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next
            node<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next
            cur<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> node

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">remove</span>(self, item):
        <span style="color:#e6db74">&#34;&#34;&#34;删除节点&#34;&#34;&#34;</span>
        cur <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
        pre <span style="color:#f92672">=</span> None
        <span style="color:#66d9ef">while</span> cur <span style="color:#f92672">is</span> <span style="color:#f92672">not</span> None:
            <span style="color:#75715e"># 找到指定元素</span>
            <span style="color:#66d9ef">if</span> cur<span style="color:#f92672">.</span>item <span style="color:#f92672">==</span> item:
                <span style="color:#75715e"># 如果第一个就是删除的节点</span>
                <span style="color:#66d9ef">if</span> <span style="color:#f92672">not</span> pre:
                    <span style="color:#75715e"># 将头指针指向头节点的后一个节点</span>
                    self<span style="color:#f92672">.</span>_head <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next
                <span style="color:#66d9ef">else</span>:
                    <span style="color:#75715e"># 将删除位置前一个节点的next指向删除位置的后一个节点</span>
                    pre<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next
                <span style="color:#66d9ef">return</span> True
            <span style="color:#66d9ef">else</span>:
                <span style="color:#75715e"># 继续按链表后移节点</span>
                pre <span style="color:#f92672">=</span> cur
                cur <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">find</span>(self, item):
        <span style="color:#e6db74">&#34;&#34;&#34;查找元素是否存在&#34;&#34;&#34;</span>
        <span style="color:#66d9ef">return</span> item <span style="color:#f92672">in</span> self<span style="color:#f92672">.</span>items()
</code></pre></div><p>示例：操作链表</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">if</span> __name__ <span style="color:#f92672">==</span> <span style="color:#e6db74">&#39;__main__&#39;</span>:
    link_list <span style="color:#f92672">=</span> SingleLinkList()
    <span style="color:#75715e"># 向链表尾部添加数据</span>
    <span style="color:#66d9ef">for</span> i <span style="color:#f92672">in</span> range(<span style="color:#ae81ff">5</span>):
        link_list<span style="color:#f92672">.</span>append(i)
    <span style="color:#75715e"># 向头部添加数据</span>
    link_list<span style="color:#f92672">.</span>add(<span style="color:#ae81ff">6</span>)
    <span style="color:#75715e"># 遍历链表数据</span>
    <span style="color:#66d9ef">for</span> i <span style="color:#f92672">in</span> link_list<span style="color:#f92672">.</span>items():
        <span style="color:#66d9ef">print</span>(i, end<span style="color:#f92672">=</span><span style="color:#e6db74">&#39;</span><span style="color:#ae81ff">\t</span><span style="color:#e6db74">&#39;</span>)
    <span style="color:#75715e"># 链表数据插入数据</span>
    link_list<span style="color:#f92672">.</span>insert(<span style="color:#ae81ff">3</span>, <span style="color:#ae81ff">9</span>)
    <span style="color:#66d9ef">print</span>(<span style="color:#e6db74">&#39;</span><span style="color:#ae81ff">\n</span><span style="color:#e6db74">&#39;</span>, list(link_list<span style="color:#f92672">.</span>items()))
    <span style="color:#75715e"># 删除链表数据</span>
    link_list<span style="color:#f92672">.</span>remove(<span style="color:#ae81ff">0</span>)
    <span style="color:#75715e"># 查找链表数据</span>
    <span style="color:#66d9ef">print</span>(link_list<span style="color:#f92672">.</span>find(<span style="color:#ae81ff">4</span>))
</code></pre></div><h2 id="三循环链表">三、循环链表</h2>
<p><img src="C:%5Cwww%5Chugo_blog%5Cpublic%5Cimg%5Cxunhaunlianbiao.jpg" alt="循环链表结构"></p>
<p>单向循环链表为单向链表的变种，链表的最后一个next指向链表头，新增一个循环。</p>
<h3 id="1-循环链表结点">1. 循环链表结点</h3>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">Node</span>(object):
    <span style="color:#e6db74">&#34;&#34;&#34;链表的结点&#34;&#34;&#34;</span>

    <span style="color:#66d9ef">def</span> __init__(self, item):
        <span style="color:#75715e"># item存放数据元素</span>
        self<span style="color:#f92672">.</span>item <span style="color:#f92672">=</span> item
        <span style="color:#75715e"># next是下一个节点的标识</span>
        self<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> None
</code></pre></div><h3 id="2-定义循环链表">2. 定义循环链表</h3>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">SingleCycleLinkList</span>(object):

    <span style="color:#66d9ef">def</span> __init__(self):
        self<span style="color:#f92672">.</span>_head <span style="color:#f92672">=</span> None

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">is_empty</span>(self):
        <span style="color:#e6db74">&#34;&#34;&#34;判断链表是否为空&#34;&#34;&#34;</span>
        <span style="color:#66d9ef">return</span> self<span style="color:#f92672">.</span>_head <span style="color:#f92672">is</span> None

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">length</span>(self):
        <span style="color:#e6db74">&#34;&#34;&#34;链表长度&#34;&#34;&#34;</span>
        <span style="color:#75715e"># 链表为空</span>
        <span style="color:#66d9ef">if</span> self<span style="color:#f92672">.</span>is_empty():
            <span style="color:#66d9ef">return</span> <span style="color:#ae81ff">0</span>
        <span style="color:#75715e"># 链表不为空</span>
        count <span style="color:#f92672">=</span> <span style="color:#ae81ff">1</span>
        cur <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
        <span style="color:#66d9ef">while</span> cur<span style="color:#f92672">.</span>next <span style="color:#f92672">!=</span> self<span style="color:#f92672">.</span>_head:
            count <span style="color:#f92672">+=</span> <span style="color:#ae81ff">1</span>
            <span style="color:#75715e"># 指针下移</span>
            cur <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next
        <span style="color:#66d9ef">return</span> count

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">items</span>(self):
        <span style="color:#e6db74">&#34;&#34;&#34; 遍历链表 &#34;&#34;&#34;</span>
        <span style="color:#75715e"># 链表为空</span>
        <span style="color:#66d9ef">if</span> self<span style="color:#f92672">.</span>is_empty():
            <span style="color:#66d9ef">return</span>
        <span style="color:#75715e"># 链表不为空</span>
        cur <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
        <span style="color:#66d9ef">while</span> cur<span style="color:#f92672">.</span>next <span style="color:#f92672">!=</span> self<span style="color:#f92672">.</span>_head:
            <span style="color:#66d9ef">yield</span> cur<span style="color:#f92672">.</span>item
            cur <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next
        <span style="color:#66d9ef">yield</span> cur<span style="color:#f92672">.</span>item

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">add</span>(self, item):
        <span style="color:#e6db74">&#34;&#34;&#34; 头部添加结点&#34;&#34;&#34;</span>
        node <span style="color:#f92672">=</span> Node(item)
        <span style="color:#66d9ef">if</span> self<span style="color:#f92672">.</span>is_empty():  <span style="color:#75715e"># 为空</span>
            self<span style="color:#f92672">.</span>_head <span style="color:#f92672">=</span> node
            node<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
        <span style="color:#66d9ef">else</span>:
            <span style="color:#75715e"># 添加结点指向head</span>
            node<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
            cur <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
            <span style="color:#75715e"># 移动结点，将末尾的结点指向node</span>
            <span style="color:#66d9ef">while</span> cur<span style="color:#f92672">.</span>next <span style="color:#f92672">!=</span> self<span style="color:#f92672">.</span>_head:
                cur <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next
            cur<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> node
        <span style="color:#75715e"># 修改 head 指向新结点</span>
        self<span style="color:#f92672">.</span>_head <span style="color:#f92672">=</span> node

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">append</span>(self, item):
        <span style="color:#e6db74">&#34;&#34;&#34;尾部添加结点&#34;&#34;&#34;</span>
        node <span style="color:#f92672">=</span> Node(item)
        <span style="color:#66d9ef">if</span> self<span style="color:#f92672">.</span>is_empty():  <span style="color:#75715e"># 为空</span>
            self<span style="color:#f92672">.</span>_head <span style="color:#f92672">=</span> node
            node<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
        <span style="color:#66d9ef">else</span>:
            <span style="color:#75715e"># 寻找尾部</span>
            cur <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
            <span style="color:#66d9ef">while</span> cur<span style="color:#f92672">.</span>next <span style="color:#f92672">!=</span> self<span style="color:#f92672">.</span>_head:
                cur <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next
            <span style="color:#75715e"># 尾部指针指向新结点</span>
            cur<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> node
            <span style="color:#75715e"># 新结点指针指向head</span>
            node<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">insert</span>(self, index, item):
        <span style="color:#e6db74">&#34;&#34;&#34; 指定位置添加结点&#34;&#34;&#34;</span>
        <span style="color:#66d9ef">if</span> index <span style="color:#f92672">&lt;=</span> <span style="color:#ae81ff">0</span>:  <span style="color:#75715e"># 指定位置小于等于0，头部添加</span>
            self<span style="color:#f92672">.</span>add(item)
        <span style="color:#75715e"># 指定位置大于链表长度，尾部添加</span>
        <span style="color:#66d9ef">elif</span> index <span style="color:#f92672">&gt;</span> self<span style="color:#f92672">.</span>length() <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span>:
            self<span style="color:#f92672">.</span>append(item)
        <span style="color:#66d9ef">else</span>:
            node <span style="color:#f92672">=</span> Node(item)
            cur <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
            <span style="color:#75715e"># 移动到添加结点位置</span>
            <span style="color:#66d9ef">for</span> i <span style="color:#f92672">in</span> range(index <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span>):
                cur <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next
            <span style="color:#75715e"># 新结点指针指向旧结点</span>
            node<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next
            <span style="color:#75715e"># 旧结点指针 指向 新结点</span>
            cur<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> node

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">remove</span>(self, item):
        <span style="color:#e6db74">&#34;&#34;&#34; 删除一个结点 &#34;&#34;&#34;</span>
        <span style="color:#66d9ef">if</span> self<span style="color:#f92672">.</span>is_empty():
            <span style="color:#66d9ef">return</span>
        cur <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
        pre <span style="color:#f92672">=</span> Node
        <span style="color:#75715e"># 第一个元素为需要删除的元素</span>
        <span style="color:#66d9ef">if</span> cur<span style="color:#f92672">.</span>item <span style="color:#f92672">==</span> item:
            <span style="color:#75715e"># 链表不止一个元素</span>
            <span style="color:#66d9ef">if</span> cur<span style="color:#f92672">.</span>next <span style="color:#f92672">!=</span> self<span style="color:#f92672">.</span>_head:
                <span style="color:#66d9ef">while</span> cur<span style="color:#f92672">.</span>next <span style="color:#f92672">!=</span> self<span style="color:#f92672">.</span>_head:
                    cur <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next
                <span style="color:#75715e"># 尾结点指向 头部结点的下一结点</span>
                cur<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head<span style="color:#f92672">.</span>next
                <span style="color:#75715e"># 调整头部结点</span>
                self<span style="color:#f92672">.</span>_head <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head<span style="color:#f92672">.</span>next
            <span style="color:#66d9ef">else</span>:
                <span style="color:#75715e"># 只有一个元素</span>
                self<span style="color:#f92672">.</span>_head <span style="color:#f92672">=</span> None
        <span style="color:#66d9ef">else</span>:
            <span style="color:#75715e"># 不是第一个元素</span>
            pre <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
            <span style="color:#66d9ef">while</span> cur<span style="color:#f92672">.</span>next <span style="color:#f92672">!=</span> self<span style="color:#f92672">.</span>_head:
                <span style="color:#66d9ef">if</span> cur<span style="color:#f92672">.</span>item <span style="color:#f92672">==</span> item:
                    <span style="color:#75715e"># 删除</span>
                    pre<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next
                    <span style="color:#66d9ef">return</span> True
                <span style="color:#66d9ef">else</span>:

                    pre <span style="color:#f92672">=</span> cur  <span style="color:#75715e"># 记录前一个指针</span>
                    cur <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next  <span style="color:#75715e"># 调整指针位置</span>
        <span style="color:#75715e"># 当删除元素在末尾</span>
        <span style="color:#66d9ef">if</span> cur<span style="color:#f92672">.</span>item <span style="color:#f92672">==</span> item:
            pre<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
            <span style="color:#66d9ef">return</span> True

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">find</span>(self, item):
        <span style="color:#e6db74">&#34;&#34;&#34; 查找元素是否存在&#34;&#34;&#34;</span>
        <span style="color:#66d9ef">return</span> item <span style="color:#f92672">in</span> self<span style="color:#f92672">.</span>items()


<span style="color:#66d9ef">if</span> __name__ <span style="color:#f92672">==</span> <span style="color:#e6db74">&#39;__main__&#39;</span>:
    link_list <span style="color:#f92672">=</span> SingleCycleLinkList()
    <span style="color:#66d9ef">print</span>(link_list<span style="color:#f92672">.</span>is_empty())
    <span style="color:#75715e"># 头部添加元素</span>
    <span style="color:#66d9ef">for</span> i <span style="color:#f92672">in</span> range(<span style="color:#ae81ff">5</span>):
        link_list<span style="color:#f92672">.</span>add(i)
    <span style="color:#66d9ef">print</span>(list(link_list<span style="color:#f92672">.</span>items()))
    <span style="color:#75715e"># 尾部添加元素</span>
    <span style="color:#66d9ef">for</span> i <span style="color:#f92672">in</span> range(<span style="color:#ae81ff">6</span>):
        link_list<span style="color:#f92672">.</span>append(i)
    <span style="color:#66d9ef">print</span>(list(link_list<span style="color:#f92672">.</span>items()))
    <span style="color:#75715e"># 添加元素</span>
    link_list<span style="color:#f92672">.</span>insert(<span style="color:#ae81ff">3</span>, <span style="color:#ae81ff">45</span>)
    <span style="color:#66d9ef">print</span>(list(link_list<span style="color:#f92672">.</span>items()))
    <span style="color:#75715e"># 删除元素</span>
    link_list<span style="color:#f92672">.</span>remove(<span style="color:#ae81ff">5</span>)
    <span style="color:#66d9ef">print</span>(list(link_list<span style="color:#f92672">.</span>items()))
    <span style="color:#75715e"># 元素是否存在</span>
    <span style="color:#66d9ef">print</span>(<span style="color:#ae81ff">4</span> <span style="color:#f92672">in</span> link_list<span style="color:#f92672">.</span>items())
</code></pre></div><h2 id="四双向链表">四、双向链表</h2>
<p>双向链表比单向链表更加复杂，它每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个链接指向下一个节点，当此节点为最后一个节点时，指向空值。</p>
<p><img src="C:%5Cwww%5Chugo_blog%5Cpublic%5Cimg%5Cshuanglian.jpg" alt="双向链表结构"></p>
<p>head 保存首地址，item 存储数据，next 指向下一结点地址，prev 指向上一结点地址。</p>
<h3 id="1-定义双向链表结点">1. 定义双向链表结点</h3>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">Node</span>(object):
    <span style="color:#e6db74">&#34;&#34;&#34;双向链表的结点&#34;&#34;&#34;</span>

    <span style="color:#66d9ef">def</span> __init__(self, item):
        <span style="color:#75715e"># item存放数据元素</span>
        self<span style="color:#f92672">.</span>item <span style="color:#f92672">=</span> item
        <span style="color:#75715e"># next 指向下一个节点的标识</span>
        self<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> None
        <span style="color:#75715e"># prev 指向上一结点</span>
        self<span style="color:#f92672">.</span>prev <span style="color:#f92672">=</span> None
</code></pre></div><h3 id="2-定义双向链表">2. 定义双向链表</h3>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">BilateralLinkList</span>(object):
    <span style="color:#e6db74">&#34;&#34;&#34;双向链表&#34;&#34;&#34;</span>

    <span style="color:#66d9ef">def</span> __init__(self):
        self<span style="color:#f92672">.</span>_head <span style="color:#f92672">=</span> None

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">is_empty</span>(self):
        <span style="color:#e6db74">&#34;&#34;&#34;判断链表是否为空&#34;&#34;&#34;</span>
        <span style="color:#66d9ef">return</span> self<span style="color:#f92672">.</span>_head <span style="color:#f92672">is</span> None

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">length</span>(self):
        <span style="color:#e6db74">&#34;&#34;&#34;链表长度&#34;&#34;&#34;</span>
        <span style="color:#75715e"># 初始指针指向head</span>
        cur <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
        count <span style="color:#f92672">=</span> <span style="color:#ae81ff">0</span>
        <span style="color:#75715e"># 指针指向None 表示到达尾部</span>
        <span style="color:#66d9ef">while</span> cur <span style="color:#f92672">is</span> <span style="color:#f92672">not</span> None:
            count <span style="color:#f92672">+=</span> <span style="color:#ae81ff">1</span>
            <span style="color:#75715e"># 指针下移</span>
            cur <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next
        <span style="color:#66d9ef">return</span> count

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">items</span>(self):
        <span style="color:#e6db74">&#34;&#34;&#34;遍历链表&#34;&#34;&#34;</span>
        <span style="color:#75715e"># 获取head指针</span>
        cur <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
        <span style="color:#75715e"># 循环遍历</span>
        <span style="color:#66d9ef">while</span> cur <span style="color:#f92672">is</span> <span style="color:#f92672">not</span> None:
            <span style="color:#75715e"># 返回生成器</span>
            <span style="color:#66d9ef">yield</span> cur<span style="color:#f92672">.</span>item
            <span style="color:#75715e"># 指针下移</span>
            cur <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">add</span>(self, item):
        <span style="color:#e6db74">&#34;&#34;&#34;向链表头部添加元素&#34;&#34;&#34;</span>
        node <span style="color:#f92672">=</span> Node(item)
        <span style="color:#66d9ef">if</span> self<span style="color:#f92672">.</span>is_empty():
            <span style="color:#75715e"># 头部结点指针修改为新结点</span>
            self<span style="color:#f92672">.</span>_head <span style="color:#f92672">=</span> node
        <span style="color:#66d9ef">else</span>:
            <span style="color:#75715e"># 新结点指针指向原头部结点</span>
            node<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
            <span style="color:#75715e"># 原头部 prev 指向 新结点</span>
            self<span style="color:#f92672">.</span>_head<span style="color:#f92672">.</span>prev <span style="color:#f92672">=</span> node
            <span style="color:#75715e"># head 指向新结点</span>
            self<span style="color:#f92672">.</span>_head <span style="color:#f92672">=</span> node

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">append</span>(self, item):
        <span style="color:#e6db74">&#34;&#34;&#34;尾部添加元素&#34;&#34;&#34;</span>
        node <span style="color:#f92672">=</span> Node(item)
        <span style="color:#66d9ef">if</span> self<span style="color:#f92672">.</span>is_empty():  <span style="color:#75715e"># 链表无元素</span>
            <span style="color:#75715e"># 头部结点指针修改为新结点</span>
            self<span style="color:#f92672">.</span>_head <span style="color:#f92672">=</span> node
        <span style="color:#66d9ef">else</span>:  <span style="color:#75715e"># 链表有元素</span>
            <span style="color:#75715e"># 移动到尾部</span>
            cur <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
            <span style="color:#66d9ef">while</span> cur<span style="color:#f92672">.</span>next <span style="color:#f92672">is</span> <span style="color:#f92672">not</span> None:
                cur <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next
            <span style="color:#75715e"># 新结点上一级指针指向旧尾部</span>
            node<span style="color:#f92672">.</span>prev <span style="color:#f92672">=</span> cur
            <span style="color:#75715e"># 旧尾部指向新结点</span>
            cur<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> node

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">insert</span>(self, index, item):
        <span style="color:#e6db74">&#34;&#34;&#34; 指定位置插入元素&#34;&#34;&#34;</span>
        <span style="color:#66d9ef">if</span> index <span style="color:#f92672">&lt;=</span> <span style="color:#ae81ff">0</span>:
            self<span style="color:#f92672">.</span>add(item)
        <span style="color:#66d9ef">elif</span> index <span style="color:#f92672">&gt;</span> self<span style="color:#f92672">.</span>length() <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span>:
            self<span style="color:#f92672">.</span>append(item)
        <span style="color:#66d9ef">else</span>:
            node <span style="color:#f92672">=</span> Node(item)
            cur <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
            <span style="color:#66d9ef">for</span> i <span style="color:#f92672">in</span> range(index):
                cur <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next
            <span style="color:#75715e"># 新结点的向下指针指向当前结点</span>
            node<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> cur
            <span style="color:#75715e"># 新结点的向上指针指向当前结点的上一结点</span>
            node<span style="color:#f92672">.</span>prev <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>prev
            <span style="color:#75715e"># 当前上一结点的向下指针指向node</span>
            cur<span style="color:#f92672">.</span>prev<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> node
            <span style="color:#75715e"># 当前结点的向上指针指向新结点</span>
            cur<span style="color:#f92672">.</span>prev <span style="color:#f92672">=</span> node

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">remove</span>(self, item):
        <span style="color:#e6db74">&#34;&#34;&#34; 删除结点 &#34;&#34;&#34;</span>
        <span style="color:#66d9ef">if</span> self<span style="color:#f92672">.</span>is_empty():
            <span style="color:#66d9ef">return</span>
        cur <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>_head
        <span style="color:#75715e"># 删除元素在第一个结点</span>
        <span style="color:#66d9ef">if</span> cur<span style="color:#f92672">.</span>item <span style="color:#f92672">==</span> item:
            <span style="color:#75715e"># 只有一个元素</span>
            <span style="color:#66d9ef">if</span> cur<span style="color:#f92672">.</span>next <span style="color:#f92672">is</span> None:
                self<span style="color:#f92672">.</span>_head <span style="color:#f92672">=</span> None
                <span style="color:#66d9ef">return</span> True
            <span style="color:#66d9ef">else</span>:
                <span style="color:#75715e"># head 指向下一结点</span>
                self<span style="color:#f92672">.</span>_head <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next
                <span style="color:#75715e"># 下一结点的向上指针指向None</span>
                cur<span style="color:#f92672">.</span>next<span style="color:#f92672">.</span>prev <span style="color:#f92672">=</span> None
                <span style="color:#66d9ef">return</span> True
        <span style="color:#75715e"># 移动指针查找元素</span>
        <span style="color:#66d9ef">while</span> cur<span style="color:#f92672">.</span>next <span style="color:#f92672">is</span> <span style="color:#f92672">not</span> None:
            <span style="color:#66d9ef">if</span> cur<span style="color:#f92672">.</span>item <span style="color:#f92672">==</span> item:
                <span style="color:#75715e"># 上一结点向下指针指向下一结点</span>
                cur<span style="color:#f92672">.</span>prev<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next
                <span style="color:#75715e"># 下一结点向上指针指向上一结点</span>
                cur<span style="color:#f92672">.</span>next<span style="color:#f92672">.</span>prev <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>prev
                <span style="color:#66d9ef">return</span> True
            cur <span style="color:#f92672">=</span> cur<span style="color:#f92672">.</span>next
        <span style="color:#75715e"># 删除元素在最后一个</span>
        <span style="color:#66d9ef">if</span> cur<span style="color:#f92672">.</span>item <span style="color:#f92672">==</span> item:
            <span style="color:#75715e"># 上一结点向下指针指向None</span>
            cur<span style="color:#f92672">.</span>prev<span style="color:#f92672">.</span>next <span style="color:#f92672">=</span> None
            <span style="color:#66d9ef">return</span> True

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">find</span>(self, item):
        <span style="color:#e6db74">&#34;&#34;&#34;查找元素是否存在&#34;&#34;&#34;</span>
        <span style="color:#66d9ef">return</span> item <span style="color:#f92672">in</span> self<span style="color:#f92672">.</span>items()
</code></pre></div>
</div>


    </main>

    
  </body>
</html>
